In most fields of endeavor today, people require access to large bodies of information. Frequently the information is textual, but it might also include pictures, graphical images or auditory signals. For example, medical records may include x-rays, ekgs, patient descriptions and CT scans. Whether the area is medicine, art history, car mechanics, or home shopping, there is a need to organize information for presentation to a user and to make that organization flexible and dynamic. An important feature of the present Intelligent Optical Navigator (ION) system is its dynamic nature. That is, as the user browses through information available in the system, both the structure of the information and the manner of presenting it is changed in response to the user's input, and this is accomplished without the need for re-programming, which typically would require the skills and expertise of a system developer. This dynamic re-structuring allows a user to organize and view information according to the user's needs and preferences. As is described below, today's technology does not provide the dynamic, flexible re-organization and presentation of information which is present in the ION system.
In today's technology, databases are often used to organize and present information (for further information on typical database technology, see Date, C., An Introduction to Database Systems, Reading: Addison-Wesley, 1-80, 1982). Most databases include only text, but more recent advances allow access to visual databases as well (see, for example, Roussopoulos, N., Faloutsos, F., and Sellis, T., An efficient pictorial database system for PSQL, IEEE Transactions on Software Engineering, vol. 14, 639-650, 1988).
A limitation of traditional database technology is that it does not allow a user to organize information dynamically to fit the user's individual needs. Once an initial structure is built into the database, access to information is limited to the pre-built structure, typically a fixed set of queries. Through a series of manipulations, a system developer can add new queries using special query languages, but a system user is restricted to the types of queries which have been built in by the system developer. In that sense, the systems are not dynamic. In addition, items of information must be accessed sequentially. If, for example, a user asks for records of patients who visited a clinic on July 3rd and who had a diagnosis of heart disease, the system would pull up perhaps 30 patient records which then would be viewed sequentially. There is no possibility of viewing the data using an organization specified by the user as the user views the data unless that organization has been pre-built into the system by a system developer. In traditional systems, it also is impossible for a user to add into the system new information about arbitrary relationships between items of data. Suppose, for example, that a user wanted to indicate that patient A is related to patient B. Unless a "related" concept already existed in the system, the information could not be added.
The advent of hypertext systems has alleviated some, but not all, of these concerns (typical hypertext systems are described in Conklin, J., Hypertext: An introduction and survey, IEEE Computer, 17-41, September, 1987). In a typical hypertext system, a user may place arbitrary links between items of information and use these links to browse through information. However, in hypertext systems, the structure is limited to simple links between two items, and views into the data cannot be changed dynamically. A user cannot dynamically devise a new structure with which to view the data without asking a system developer to write new code. The ability to devise new structures is often important because it is the structure which helps give users an understanding of where they are currently located and where they can move within a space of data.
Accordingly, a problem with today's technology for information organization and presentation is that it lacks the flexibility to provide the capability for a user to dynamically re-arrange the presentation based upon the user's needs. For example, suppose that a user wishes to view travel information about different cities. With a typical database system, the user could specify certain characteristics about a city such as size and weather, and retrieve information about cities which meet those characteristics. In a typical hypertext system, the user could point to a map to indicate a geographical area, retrieve information about a city in that region, browse sequentially through information on its hotels, weather, and entertainment, and then jump to information which supplements the entertainment information currently on the screen. It would be difficult, however, to view simultaneously three or four cities which are organized on the user's monitor according to a structure defined by the user, for example, to create a definition of city-similarity and use the newly-created definition to find cities similar to the one on view. These functions require the ability of a system to dynamically re-organize based on user needs.
The present system circumvents these difficulties by providing a flexible structure for storing multi-media information and a series of presentation modes, each of which provides a different view of the information and an organization which can be altered dynamically by the user. The preferred system also provides user modeling (for example, it can monitor user activity to determine preferences and incorporate these preferences into future interaction with the user) and easy movement between related information in the multiple presentation modes (for example, a user may easily view the same information from the perspectives of two or three different presentation modes). The present system can be integrated with database or hypertext systems to serve as an intelligent front end to these systems and to provide the structure and dynamic re-organization capabilities desired while providing access to previously stored information. In addition to its use as an intelligent front end to a database, it can be integrated into many other types of systems such as tutorial, training, or simulation systems.
There are six presentation modes available in the current system. These are referred to in the present application as the Space Explorer, Nearest Neighbor, Focus, Dynamic Image Scanner, Living Equations, and SNETS systems. Each presentation mode will be described briefly below and compared with prior art which relates most closely to the mode.
The present Space Explorer system provides a method for organizing information into an n-dimensional space where the dimensions and methods of navigation through the space are selected by a user and may be changed dynamically. For example, suppose that a user wished to browse through information on art history. With the Space Explorer system, the user could decide to view only information on 20th century artists from the United States and then could ask the system to structure the information according to artist, medium and art-style. The Space Explorer system then would present a "three dimensional space" where the dimensions are artist, medium and art-style. A center work of art would be surrounded by three satellites, each differing from the center on one of the selected dimensions. The user then could navigate through the space by changing values on any of the dimensions displayed, thus causing the entire space to be re-organized dynamically. For example, if the user changed artist to "Chagall", all presented works of art would for that moment become "Chagall" pieces of art, with the other dimension values remaining intact. Navigation could also be accomplished by altering the dimensions, selecting new dimensions or adding dimensions to the current structure.
The ability to provide a structure based on an n-dimensional space and to dynamically alter the structure are unique characteristics of the Space Explorer system. Sustik and Brooks (Sustik, J., Brooks, T., Retreiving Information with Interactive Videodiscs, Journal of the American Society for Information Science, 34, 424-432, 1983) describe an idea in which a user can browse through information by gradually changing a value along a continuum such as color. However, only one dimension can be selected at a time, and the idea was not developed into a system. Educomp has released a "Macintosh" computer demo under the trademark "Mac a Mug" in which a graphic representation of a face is presented, and a user can browse through possible faces by altering characteristics such as hair style (MacGuide, Vol 1, page 179A, 1988). In the "Mac a Mug" system, the potential characteristics are pre-defined and may not be changed. None of these systems allows for dynamic re-organization of an n-dimensional space.
The preferred Nearest Neighbor system allows a user to create and use definitions of similarity in order to organize a plurality of concepts dynamically according to their similarity. For example, a user might select a concept "car" and a definition of similarity which indicates that another car is similar to the first if it is made by the same manufacturer, has roughly the same price and roughly the same engine size. The user might also indicate that seating capacity should be considered but should be a lower priority in a similarity definition. Using these criteria, the Nearest Neighbor system can retrieve information on several cars which are most similar to the initially selected car. An important component of the system is the ability of a user to create similarity definitions and to use a plurality of definitions in a single retrieval session. Thus, the system is dynamic and can be tailored to an individual's needs.
The Nearest Neighbor system differs from databases and hypertext systems by providing dynamically changing definitions of similarity and using them to structure the data. In database systems, queries must be predefined by a system developer and cannot be changed by a system user, and there is no concept of a "similarity" query. In hypertext systems a user may follow links but may not make similarity queries. Another example of prior art is pattern recognition systems which help to categorize objects by their attributes but do not allow a user to specify arbitrary similarity definitions or to use newly created definitions to access related data (see for example, Duda, R., and Hart, P., Pattern Classification and Scene Analysis, 1-9, New York, Wiley & Sons, 1973). They typically are quite slow, require complex mathematical analysis, and are used most often to perform image analysis. Thus, the Nearest Neighbor system provides a new way of thinking about and organizing information which can be very useful because it is flexible and can be molded to a user's needs.
The preferred Focus system allows a user to view a real world object from a number of different perspectives. For example, a user might want to view a car from a number of different positions and distances; the Focus system makes it easy for a user to select and change the position and distance. An important part of the Focus system is the flexibility provided in selection of real world object characteristics and values which are of interest in a particular situation and which provide access to a set of perspectives. A typical prior art system might provide access to multiple views of an object, but the views are pre-built and cannot be changed dynamically.
For example, a training system identified by the trademark "Electric Cadaver" (Byte, p. 14, August, 1988) provides a medical student with the ability to view anatomy by zooming in on a body part, rotating the part and viewing it via x-ray or graphics. It supports only limited editing of text and animation sequences. The Cardiac Imaging Project developed by Lynch (MACUSER, p. 261, May, 1988) provides animation sequences of anatomy and physiology of the heart, but these may only be viewed sequentially. A system identified by the name "HeartLab" system (see Bergeron, B., Greenes, R., HeartLab and EkgLab) Skill-Building Simulations in Cardiology, Demonstrations Digest, 11th Annual Symposium on Computer Applications in Medical Care, 29-30, 1987) provides graphic views of the heart for use in training in heart disease. When an area of the heart is selected, corresponding heart sounds may be heard. Unlike the Focus system, these systems are all domain dependent. The Search/Retrieval System described in U.S. Pat. No. 4,736,308 entitled "Search/Retrieval System" provides multiple pieces of information simultaneously. However, information may only be textual, and there is not an intelligent aid provided to help select the information for display.
Other examples of prior art may be found in computer-aided design (CAD) and computer-aided engineering (CAE) systems used to develop and manipulate representations of physical objects (see for example, Myklebust, A., Mechanical computer-aided engineering, IEEE Computer Graphics and Applications, 24-25, March, 1988, and Gossard, D., Zuffante, R., and Sakurai, H., Representing Dimensions, Tolerances, and Features in MCAE Systems, IEEE Computer Graphics and Applications, 51-59, March, 1988). The representations used in these systems are limited to line drawings or solid renderings based on computer graphics. The preferred Focus system is not limited in this regard, but can present to a user any video image or sequence. It also allows a user to specify dynamically a desired representation, context and level of detail.
In all of these prior art systems, the views available are built in by a system developer and generally may not be changed by a user. In contrast, the present Focus system provides the user with dynamic control over organization of presentation and method of navigating through the information. For example, the user may decide at one moment to view an object according to an organization based on distance from the object and position of the object, and in the next moment to view the object according to an organization based on functional use of the object. The user may dynamically navigate through the information by changing an object attribute in the existing organization or by changing the entire organization. The advantage of this system is that the user selects the structure most helpful for the user's current situation, and the new structure is implemented immediately.
The present Dynamic Image Scanner system allows a user to navigate through a plurality of concepts by manipulating graphical representations of concepts. For example, a user who is interested in "chairs" might be presented with a graphical representation of a "standard chair." The user might manipulate the image graphically to indicate a chair of a greater width. The system can interpret the manipulation and use it to access information about a chair which matches the new graphical representation; perhaps the new chair might be a love seat. The Dynamic Image Scanner system is particularly useful in browsing through information in situations in which it is difficult to describe verbally the modifications one has in mind. It might be hard to describe a chair which has a particular form but easy to draw the form. The system is dynamic and flexible because the user has the ability not only to make graphical manipulations but also to select the relationship desired between graphical interpretation and concepts selected. That is, in one case, the user might ask for a chair which is closest in form to the one drawn. In another case, the user might ask for information about the process of building such a chair.
There are many systems available which allow a user to make graphic manipulations on a screen. For example, graphics packages allow a user to draw complex objects, and CAD/CAM systems allow a user to manipulate 2-d and 3-d images. However, these packages have no method of interpreting manipulations and using interpretations to access related information. The "Electric Cadaver" system mentioned above allows a user to manipulate a nerve on a graphic representation of the body and access information on related disorders. However, there is only one type of manipulation available, and only one type of relationship available. In addition, it is tied to a specific medical application. Hypertext and database systems do not incorporate graphic manipulation into their querying techniques.
The preferred Living Equations system allows a user to examine both numerical and graphical representations of an equation, to manipulate the equation by altering the form of the equation, the values, or the units, and to examine relationships between terms of the equation and between concepts which are available in other systems such as the SNETS system described below. There are systems available which provide much more complex analyses of mathematical relationships but which are not as flexible. For example, they may be tied to a particular domain. A case in points is a system identified by the name "STEAMER" system (see Wenger, E., Artificial Intelligence and Tutoring Systems, Los Altos, Morgan Kaufmann, 79-88, 1987) which provides an interactive, inspectable simulation of a steam propulsion plant using computer graphics. A user can manipulate a variable such as temperature and see the results on the rest of the system. There are also packages which perform complex mathematical operations. For example, a system identified by the trademark "MACSYMA" (see advertising brochure from Symbolics, Inc.) performs algebra and trigonometry, calculus and differential equations and numerical analysis. By contrast, the Living Equations system handles single equations but provides a variety of related information about the equations. For example, when examining an equation on Poiseuille's law, a user can jump to a portion of a semantic net related to the changes in flow observed when manipulating the law. Related information which can be accessed includes motion sequences, graphics and pictures as well as text to provide a better understanding of the relationships observed. In addition, the Living Equations system is not limited to one domain such as steam plants, but can be applied across a variety of domains.
The preferred SNETS system allows a user to create, display, edit, store and browse through semantic nets and to integrate semantic nets with other forms of viewing information. A semantic net is a knowledge representation which displays concepts and relationships between them in a graphical form in which concepts are represented as nodes and relationships are represented as links between nodes (see, for example, Rich, E., Artificial Intelligence, New York: McGraw-Hill, 215-222, 1983). There are several semantic net building tools available under a variety of names such as "SemNet" (see Fisher, K., Faletti, J., Thornton, R., Patterson, H., Lipson, J., and Spring, C., Computer-based knowledge representation as a tool for students and teachers, draft of paper, 1987), "Learning Tool" (see Kinko's Academic Courseware Exchange Spring 1988 Catalog, page 49, 1988), "NoteCards" (see Halasz, F., Moran, T., and Trigg, R., NoteCards in a Nutshell, ACM, 45-52, June, 1987), "Unified Medical Language System" (Komorowski, H., Greenes, R., Barr, C., and Pattison-Gordon, E., Browsing and Authoring Tools for a Unified Medical Language System, Harvard Medical School, Brigham and Women's Hospital, Boston, MA), and "Neptune" (Delisle, N., and Schwartz, M., Neptune: a Hypertext System for CAD Applications, Technical Report No. CR-85-50, Computer Research Laboratory, Tektronix Laboratories, 1986).
All of these tools (including the SNETS system) allow a user to create semantic nets, to add and delete nodes and links and to browse through semantic nets. However, none of the systems provides the flexibility of the browsing capabilities available in the SNETS system. The "NoteCards" system referred to above allows navigation by following links and has a limited searching capability based on keyword matching. The "SemNet" system provides no capability to select sub-portions of the network. The system available under the name "Learning Tool" provides only three link-types and limited database-type queries. The "Unified Medical Language Systems" provides a "fish-eye" view of a node and its relationships. With this type of view, only closely related nodes are displayed. The "Neptune" system allows depth-first traversal and the ability to limit link types during a search. A major difference between these systems and the SNETS system is the availability of multiple methods of navigation in the SNETS system and the fact that views may be selected via a natural language interface. The SNETS system allows a user to view selected portions of a semantic net such as "causal links only," or "only concepts related to thunderstorms." A user may request information related to a particular concept and may ask to view the concept along with all or a selected subset of link-types connected to the concept. The depth of links also may be specified. The user can also ask to see that portion of the net which connects two selected concepts. Again, in this case, the link-types of interest may be selected as well. Additional methods of navigation include the ability to view all portions of a semantic net residing in a single knowledge base or multiple knowledge bases. The preferred system also is able to recognize misspellings.
The presentation modes described above are enhanced by the addition of a preferred User Modeling system which provides a set of data structures and a methodology to allow a system to monitor a user's responses and to modify interaction with a user depending upon responses. For example, a system might determine that a user often requests information in a visual form and almost never requests a graphic form. When several forms are available, the system might present information initially in a visual form to match the user's typical preferences. The present User Modeling system also can be used to determine when to initiate interaction with a presentation mode and to select a mode which fits a particular context. For example, the User Modeling system might be used to examine an individual's user history, determine what concepts are not understood and select a presentation mode best able to communicate those concepts. Within a particular presentation mode, the present User Modeling system can help make decisions such as the way in which information should be displayed to a particular user, and it can record relevant information about a user's activities while interacting with the presentation mode.
There has been much prior art in the area of intelligent tutoring (see, for example, Wenger, E., Artificial Intelligence and Tutoring Systems, Los Altos: Morgan Kaufmann Publishers, 3-25 and 427-432, 1987). The prior art includes systems which perform user modeling and which use this information to teach skills to an individual. The present User Modeling system augments rather than competes with this prior art. That is, it provides a structure which allows techniques developed in the prior art to be combined with the present Intelligent Optical Navigation (ION) system. For example, the ION system could be used within a context of a tutorial program where some of the teaching techniques are defined by prior art but use the Space Explorer and Nearest Neighbor systems. In addition, the present User Modeling system provides a user modeling methodology specific to multi-media systems and to the ION system. This is a methodology which is not present in prior art.